package com.tql.SortTest;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;

public class Test {
    public static void main(String[] args) {
        int []arr={1,2,3,4,5,6,7};
        int[] tartet1 = getTartet2(arr,10);
        System.out.println(tartet1[0]+""+tartet1[1]);
        System.out.println(FeiBoNQ1(5));
    }
    //冒泡排序
    public static void bubbleSort(int []arr){
        for (int i = 0; i <arr.length ; i++) {
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j+1]>arr[j]){
                    int temp=arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=temp;
                }
            }
        }
    }
    //选择排序
    public static void SelectionSort(int []arr){
        if(arr.length==0){
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            int minIndex=i;
            for (int j = i; j <arr.length ; j++) {
                if(arr[j]<arr[minIndex]){
                    minIndex=j;
                }
            }
            int temp=arr[minIndex];
            arr[minIndex]=arr[i];
            arr[i]=temp;
        }
    }
    //二分查找
    public int search(int[] nums, int target) {
      int low=0,heigh=nums.length-1;
      while(low<=heigh){
          int mid=(heigh-low)/2+low;
          if(nums[mid]==target){
              return mid;
          }else if (nums[mid]<target){
              low=mid+1;
          }else {
              heigh=mid-1;
          }
      }
        return -1;
    }
    //136. 只出现一次的数字
    public int singleNumber(int[] nums) {
        int res=0;
        for(int n:nums){
            res=res^n;
        }
        return res;
    }
    //20. 有效的括号
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (char c:s.toCharArray()){
            if(c=='('){
                stack.push(')');
            }else if(c=='['){
                stack.push(']');
            }else if(c=='{'){
                stack.push('}');
            }else if(stack.isEmpty()||stack.pop()!=c){
                return false;
            }
        }
        return stack.isEmpty();
    }
    public int fib(int n) {
        if(n<=1) return n;
        int []arr=new int[n+1];
        arr[0]=0;
        arr[1]=1;
        for (int i = 2; i <=n ; i++) {
            arr[i]=arr[i-1]+arr[i-2];
        }
        return arr[n];
    }
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int sum = 0;
        for (int num : nums) {
            if (sum > 0)
                sum += num;
            else
                sum = num;
            res = Math.max(res, sum);
        }
        return res;
    }
    //统计素数个数，暴力算法
    public static int countSushu(int n){
        int count=0;
        if(n==1){
            return 1;
        }
        for (int i = 2; i <n; i++) {
            count+=isPrime(i)?1:0;
        }
      return count;
    }

    public static boolean isPrime(int i) {
        for (int j = 2; j <i ; j++) {
            if(i%j==0){
                return false;
            }
        }
        return true;
    }
    //有序数组去重
    public static int deleteDou(int []nums){
        if(nums.length==0){
            return 0;
        }
        int index=0;
        for (int last = 0; last < nums.length; last++) {
            if(nums[index]!=nums[last]){
                index++;
                nums[index]=nums[last];
            }
        }
        return index;
    }
    //返回数组中心下表
    public static int centerIndex(int []nums){
        if(nums.length==0){
            return -1;
        }
        int totle=0;
        int sum= Arrays.stream(nums).sum();
        for (int i = 0; i <nums.length ; i++) {
            totle+=nums[i];
            if(totle==sum){
                return i;
            }
            sum-=nums[i];
        }
        return -1;
    }
    //二分查找 ，平分跟
    public static int binarySearch(int x){
        int index=-1,left=0,right=x;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(mid*mid<x){
                index=mid;
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return -1;
    }
    //无序数组target求和 借用HashMap
    public static int[] getTartet(int []nums,int target){
        HashMap<Integer,Integer> params = new HashMap<Integer,Integer >();
        if(nums.length==0){
            return null;
        }
        for (int i = 0; i < nums.length; i++) {
            Integer integer = params.get(target - nums[i]);
            if(integer==null){
                params.put(nums[i],i);
            }else{
                return new int[]{integer,i};
            }

        }
        return null;
    }
    //有序数组target求和 借用二分查找
    public static int[] getTartet1(int []nums,int target){
        for (int i = 0; i <nums.length ; i++) {
            int left=i,right=nums.length-1;
            while(left<=right){
                int mid=left+(right-left)/2;
                if(nums[mid]==target-nums[i]){
                    return new int[]{i,mid};
                }else if(nums[mid]<target-nums[i]){
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }
        }
        return null;
    }
    //双向指针,左右
    public static int[] getTartet2(int []nums,int target){
        if(nums.length==0)return null;
        int left=0;
        int right=nums.length-1;
        while(left<right){
            if(nums[left]+nums[right]==target){
                return new int[]{left,right};
            }else if(nums[left]+nums[right]>target){
                right--;
            }else{
                left++;
            }
        }
        return null;
    }
    //斐波那契数列，1.递归
    public static int FeiBoNQ(int n){
        if(n==1)return 1;
        if(n==2) return 1;
        return FeiBoNQ(n-1)+FeiBoNQ(n-2);
    }
    //斐波那契数列，2.双向指针
    public static int FeiBoNQ1(int n){
      int left=1,right=1;
      int res=0;
        for (int i = 2; i <n; i++) {
            res=left+right;
            left=right;
            right=res;
        }
      return res;
    }

}
